<!DOCTYPE html>
<html lang="zh">

<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1">
  <title>
    
    队列（Queue） - DSRBLOG
    
  </title>
  

  
  
  <link href="atom.xml" rel="alternate" title="DSRBLOG" type="application/atom+xml">
  <link rel="stylesheet" href="asset/css/style.min.css">
  <link rel="stylesheet" href="asset/css/doc.css">
  <script src="asset/app.js"></script>


</head>

<body> <section class="ct-body">
	<div class="container">
		<div class="columns is-variable bd-klmn-columns is-4 is-centered">
			<div class="column is-four-fifths">
				<div class="post-body single-content">
					
					<h1 class="title">
						队列（Queue）
					</h1>


					<div class="media">
						
						
						<div class="media-content">
							<div class="content">
								<p>
									<span class="date">2022/03/11 00:57 上午</span>
									

									

									<br />
									<span class="tran-tags">Tags:</span>&nbsp;
									
									<a class="tag is-link is-light">#数据结构与算法</a>
									

								</p>
							</div>
						</div>

					</div>
				</div>
				<article class="markdown-body single-content">
					<h2><a id="%E6%8A%BD%E8%B1%A1%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B%E9%98%9F%E5%88%97%E7%9A%84%E5%AE%9A%E4%B9%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>抽象数据类型队列的定义</h2>
<p><img src="media/16469314692426/16471131281850.jpg" alt="" /></p>
<p><strong>例如：</strong> Q = ( a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>, ......, a<sub>n-1</sub>, a<sub>n</sub> )</p>
<ul>
<li>
<p>队列是只能在表的一端进行插入运算（<strong>队尾入队</strong>），在表的另一端进行删除运算的线性表（<strong>队头出队</strong>）</p>
</li>
<li>
<p>表尾即<strong>a<sub>n</sub></strong> 端，称为<strong>队尾</strong>；表头即<strong>a<sub>1</sub></strong> 端，称为<strong>队头</strong>；它是一种先进先出（FIFO）的线性表</p>
</li>
</ul>
<h2><a id="%E9%93%BE%E9%98%9F%E5%88%97" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>链队列</h2>
<h3><a id="%E9%93%BE%E9%98%9F%E5%88%97%E7%9A%84%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>链队列的存储结构</h3>
<pre class="line-numbers"><code class="language-c">//创建链队列结构
typedef struct QNode
{
    QElemType data;     //数据域
    struct QNode *next; //指针域
} QNode, *QueuePtr;

typedef struct
{
    QueuePtr front; //队头，指向头结点
    QueuePtr rear;  //队尾，指向尾结点
} LinkQueue;
</code></pre>
<h3><a id="%E9%93%BE%E9%98%9F%E5%88%97%E7%9A%84%E5%9F%BA%E6%9C%AC%E6%93%8D%E4%BD%9C" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>链队列的基本操作</h3>
<pre class="line-numbers"><code class="language-c">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int QElemType;

//创建链队列结构
typedef struct QNode
{
    QElemType data;     //数据域
    struct QNode *next; //指针域
} QNode, *QueuePtr;

typedef struct
{
    QueuePtr front; //队头，指向头结点
    QueuePtr rear;  //队尾，指向尾结点
} LinkQueue;

//初始化
void InitQueue(LinkQueue *Q);
//销毁
void DestroyQueue(LinkQueue *Q);
//清空
void ClearQueue(LinkQueue *Q);
//判断队空
Status QueueEmpty(LinkQueue Q);
//获取队列长度
int QueueLength(LinkQueue Q);
//获取队头
Status GetHead(LinkQueue Q, QElemType *e);
//入队（队尾入队）
void EnQueue(LinkQueue *Q, QElemType e);
//出队（队头出队）
void DeQueue(LinkQueue *Q, QElemType *e);
//遍历队列
void QueueTraverse(LinkQueue Q);

int main()
{
    LinkQueue Q;
    QElemType e;
    InitQueue(&amp;Q);
    EnQueue(&amp;Q, 10);
    EnQueue(&amp;Q, 20);
    EnQueue(&amp;Q, 30);
    EnQueue(&amp;Q, 40);
    QueueTraverse(Q);

    DeQueue(&amp;Q, &amp;e);
    QueueTraverse(Q);
    return 0;
}

//初始化，明确头结点和尾结点的指向
void InitQueue(LinkQueue *Q)
{
    Q-&gt;front = (QNode *)malloc(sizeof(QNode));
    if (!Q-&gt;front)
    {
        printf(&quot;初始化失败&quot;);
        return;
    }
    Q-&gt;rear = Q-&gt;front;
    Q-&gt;front-&gt;next = NULL; //头结点的指针域置为空
}
//销毁
void DestroyQueue(LinkQueue *Q)
{
    while (Q-&gt;front)
    {
        Q-&gt;rear = Q-&gt;front-&gt;next;
        free(Q-&gt;front);
        Q-&gt;front = Q-&gt;rear;
    }
}
//清空
void ClearQueue(LinkQueue *Q)
{
    QueuePtr cur, next;
    if (Q-&gt;front == Q-&gt;rear)
    {
        printf(&quot;队空&quot;);
        return;
    }
    cur = Q-&gt;front-&gt;next; // cur指向首元结点
    while (cur)
    {
        next = cur-&gt;next;
        free(cur);
        cur = next;
    }
    Q-&gt;front-&gt;next = NULL;
    Q-&gt;rear = Q-&gt;front;
}
//判断队空
Status QueueEmpty(LinkQueue Q)
{
    if (Q.front == Q.rear)
    {
        printf(&quot;队空&quot;);
        return TRUE;
    }
    return FALSE;
}
//获取队列长度
int QueueLength(LinkQueue Q)
{
    int i = 0;
    QueuePtr cur = Q.front-&gt;next; //将cur置于首元结点
    if (cur)
    {
        cur = cur-&gt;next;
        i++;
    }
    return i;
}
//获取队头
Status GetHead(LinkQueue Q, QElemType *e)
{
    if (Q.front == Q.rear)
    {
        printf(&quot;队空&quot;);
        return FALSE;
    }
    *e = Q.front-&gt;next-&gt;data;
    return TRUE;
}
//入队
void EnQueue(LinkQueue *Q, QElemType e)
{
    QueuePtr S = (QNode *)malloc(sizeof(QNode));
    if (!S)
    {
        printf(&quot;空间分配失败&quot;);
        return;
    }
    S-&gt;data = e;
    S-&gt;next = NULL;
    Q-&gt;rear-&gt;next = S; //连接到新结点
    Q-&gt;rear = S;       //指向新的队尾
}
//出队
void DeQueue(LinkQueue *Q, QElemType *e)
{
    QueuePtr cur;
    if (Q-&gt;front == Q-&gt;rear)
    {
        printf(&quot;队空&quot;);
        return;
    }
    cur = Q-&gt;front-&gt;next;
    *e = cur-&gt;data;
    Q-&gt;front-&gt;next = cur-&gt;next;
    //判断出队元素是否是最后一个元素
    if (cur == Q-&gt;rear)
    {
        Q-&gt;rear = Q-&gt;front;
    }
    free(cur); //释放出队元素所占的空间
}

//遍历队列
void QueueTraverse(LinkQueue Q)
{
    QueuePtr cur = Q.front-&gt;next; // cur指向首元结点
    while (cur)
    {
        printf(&quot;%d &quot;, cur-&gt;data);
        cur = cur-&gt;next;
    }
    printf(&quot;\n&quot;);
}
</code></pre>
<h2><a id="%E5%BE%AA%E7%8E%AF%E9%98%9F%E5%88%97" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>循环队列</h2>
<p>在顺序队中，当尾指针已经到了数组的上届，不能再有入队操作，但顺序队进行过出队操作，实际数组中还有空位置，称为“假溢出”，采用循环顺序队列来解决“假溢出”<br />
<img src="media/16469314692426/16471248289441.jpg" alt="" /></p>
<h3><a id="%E9%98%9F%E7%A9%BA%E6%9D%A1%E4%BB%B6" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>队空条件</h3>
<p><code>front = rear</code>（初始化时：<code>front = rear</code>）</p>
<ul>
<li>仅在初始化时<code>front = rear</code>代表队空</li>
<li>非初始化时可以通过<strong>入队、出队操作</strong>、<strong>计数器</strong>或<strong>空单元格</strong>进行判断</li>
</ul>
<h3><a id="%E9%98%9F%E6%BB%A1%E6%9D%A1%E4%BB%B6" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>队满条件</h3>
<p><code>front = (rear + 1) % N </code>（<code>N = maxsize</code>）</p>
<ul>
<li>通过空置一个单元格进行判断</li>
<li>队空时头尾相同，队慢时头尾差值为<code>N - 1</code>，<code>N</code>为空间实际存储容量</li>
<li><code>front</code>总是指向空的单元格</li>
</ul>
<h3><a id="%E9%98%9F%E5%88%97%E9%95%BF%E5%BA%A6" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>队列长度</h3>
<p><code>L = (N + rear - front) % N</code></p>
<h3><a id="%E6%8C%87%E9%92%88%E5%8F%98%E5%8C%96%E8%A7%84%E5%BE%8B" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>指针变化规律</h3>
<p><code>rear</code> = <code>(rear + 1) % N</code><br />
<code>front</code> = <code>(front + 1) % N</code></p>
<p><img src="media/16469314692426/16471253094337.jpg" alt="" /></p>

				</article>
				<div class="comments-wrap">
					<div class="share-comments">
						

						

						
					</div>
				</div><!-- end comments wrap -->
			</div>
		</div><!-- end columns -->
	</div><!-- end container -->
</section>  














<script src="asset/prism.js"></script>









</body>

</html>